package 三角形的最大周长;

import java.util.Arrays;

/**
 * 三角形的最大周长
 * <p>
 * 给定由一些正数（代表长度）组成的数组arr，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
 * 如果不能形成任何面积不为零的三角形，返回0。
 * <p>
 * 三角形条件：a+b > c
 * 排序 -> 从后向前滑动窗口
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println("res = " + largestPerimeter(new int[]{5, 10, 20, 7, 9}));
        System.out.println("res = " + largestPerimeter(new int[]{5, 10, 20, 7, 9}));


    }

    /**
     * 贪心算法
     */
    private static int largestPerimeter(int[] arr) {

        sort(arr, 0, arr.length-1);
        System.out.println("sorted = " + Arrays.toString(arr));

        for (int i = arr.length-1; i >=2; i--) {
            if (arr[i-2] + arr[i-1] > arr[i]) {
                return arr[i] + arr[i-1] + arr[i-2];
            }
        }

        return 0;
    }

    private static void sort(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }

        int v = arr[start];
        int l = start, r = end;

        while (l < r) {
            while (l < r && arr[r] >= v)
                r--;
            swap(arr, l, r);

            while (l < r && arr[l] <= v)
                l++;
            swap(arr, l, r);
        }

        sort(arr, start, l - 1);
        sort(arr, l + 1, end);
    }

    private static void swap(int[] arr, int l, int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }


}
